#include <iostream>

template<typename T> int partition(T *arr,int n);
template<typename T> int quicksort(T *arr,int n);
template<typename T> int easysort1(T *arr);
template<typename T> int easysort2(T *arr);

int main (int argc, char *argv[]){
    double A[5]={1.3 ,2.7 ,0.8 ,2.7 ,9.4};
    for(int i=0;i<5;i++)
    std::cout<<A[i]<<", ";
    std::cout<<std::endl;
    quicksort(A, 5);
    for(int i=0;i<5;i++)
    std::cout<<A[i]<<", ";
    std::cout<<std::endl;
    return 0;
}

template<typename T> int quicksort(T *arr,int n){
    if(n>3){
        int p = partition(arr,n);
        quicksort(arr,p);
        quicksort(arr+p+1, n-p-1);
    }
    else if(n==3)
        easysort1(arr);
    else
        switch(n){
            case 1:return 0;
            case 2:easysort2(arr);
            default:return -1;
        }
    return 0;
}

template<typename T> int easysort1(T *arr){
    if(arr[0]<arr[1]){
        if(arr[0]>arr[2]){
            T tmp=arr[0];
            arr[0]=arr[2];
            arr[2]=tmp;
        }
        easysort2(arr+1);}
    else{
        easysort2(arr);
        easysort2(arr+1);
    }
    return 0;
}

template<typename T> int easysort2(T *arr){
    if(arr[0]>arr[1]){
        T tmp=arr[0];
        arr[0]=arr[1];
        arr[1]=tmp;
    }
    return 0;
}

template<typename T> int partition(T *arr, int n){
    int left = 0;
    int right = n-1;
    T pivat = arr[0];
    while(left!=right){
        while(arr[right]>=pivat && right>left)
        right--;
        while(arr[left]<=pivat && left<right)
        left++;
        if(right>left){
            T tmp;
            tmp=arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
    }
    arr[0]=arr[left];
    arr[right]=pivat;
    return left;
}
